package binary_tree.LeetCode;

public class Num450 {
    public  int maxNum(TreeNode root){
        //找到以某个节点为根节点的左子树，找到左树中最大的数
        root=root.left;
        while(root.right!=null){
            root=root.right;
        }
        return root.val;
    }
    //找到以某个节点为根节点的右子树，找到右数种最小数
    public int minNum(TreeNode root){
        root=root.right;
        while(root.left!=null){
            root=root.left;
        }
        return root.val;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        //递归的终止条件
    if(root==null){
        return null;
        //当key值大于根节点的值时，在右树中删除
    }if(key>root.val){
        root.right=deleteNode(root.right,key);
        //当key值小于根节点时，在左树中删除
        }else if(key< root.val){
        root.left=deleteNode(root.left,key);
        }else{
        //找到此节点并且删除他，
        if(root.left==null&&root.right==null){
            //当树中只有根节点时，找到他直接删除
            root=null;
        }else if(root.right!=null){
            //r如果此节点有右子树，找到右子树中的最小值替换他并且删除他。
            root.val=minNum(root);
            root.right=deleteNode(root.right, root.val);
        }else {
            //如果此节点有左子树，找到此节点的左子树中的最大值并且删除他
            root.val=maxNum(root);
            root.left=deleteNode(root.left, root.val);
        }
        }
    return root;
    }
}
